package com.cskaoyan.javase.recursion._1advantage;

/**
 * 递归的思想,以及递归的优缺点
 * 引例：使用递归计算N（N>=1）的阶乘（factorial）
 *
 * 如果用循环怎么写代码?
 * 需要知道循环的次数,以及循环执行的语句,就可以写出循环了
 * n! = n * (n-1) * (n-2) * ... * 1;
 * 相当于n个数相乘,但是每乘一次就减1
 * 循环n次,然后用循环控制变量进行累乘
 *
 * 要想用递归求解,需要怎么办呢?
 * 需要找到递归的递归体以及递归的出口
 *
 * 怎么找到递归体呢?
 * 递归体相对于原本的问题/原本的需求,它们是什么关系?
 * 是分解后的小规模问题和大规模问题的区别
 *
 * 所以递归的思想/本质是分解，是将大问题分解为小问题，然后求解
 * 只要分解的问题足够小，小到可以直接得出结果
 * 最后把所有的小规模问题的解组合起来，就得到大规模问题的解
 * n! = n * (n - 1)!
 * (n - 1)! = (n-1) * (n-2)!
 * ....
 * 2! = 2
 * 1! = 1
 *
 * 设n的阶乘为f(n)
 * 以上分解过程，就可以得出递归体和递归的出口：
 * 递归体： f(n) = n * f(n-1)
 * 递归的出口: f(1) = 1
 *
 * 不难发现递归的优点是：
 *      1.递归的代码会非常简洁，这是最直观的。
 *      2.人在解决问题的时候，都会下意识的分解问题。
 *          递归的思想很符合人的思维，用递归求解一个问题的思路很容易被人理解。
 *          接第二条，一旦能够找打分解问题的思路，递归会非常好用。
 *
 * 当然递归的缺点也非常明显：
 *      1.不用递归时，往往一个方法就能解决问题。而递归会调用多个方法，占用大量栈内存，且明显存在重复计算，效率低。
 *      也就是说，使用递归求解一个问题，是花费更多的资源，获取更低效率的解决
 *      时间和空间复杂度都不占优势，既占用空间效率还低。
 *
 *      2.栈溢出错误警告！递归很危险，一旦栈溢出是严重错误！
 *
 * 综上，递归是一把伤人亦伤己的利器，实际开发中不要随意使用递归
 *      使用递归要深思熟虑递归的深度和出口，避免栈溢出错误
 *      但是递归在开发中确实有独特的使用场景，很多时候不用递归求解是很难找到其它思路。
 *
 * 递归是计算机出现之后，利用计算机的庞大算力，采取暴力的手段进行问题求解的方式。
 *
 * @since 17:21
 * @author wuguidong@cskaoyan.onaliyun.com
 */
public class Demo {
    public static void main(String[] args) {
        System.out.println(factorialLoopSolution(10));
        System.out.println(factorial(10));
    }

    public static long factorial(int n) {
        // 先写递归的出口
        if (n == 1) {
            return 1;
        }
        return n * factorial(n - 1);
    }

    public static long factorialLoopSolution(int n) {
        // 阶乘就是累乘
        int product = 1;
        for (int i = 1; i <= n; i++) {
            product *= i;
        }
        return product;
    }
}
